package com.atguigu.distributed.lock.leecode.dinamic;

public class HarvestingMachine {
    public static void main(String[] args) {
//        int[][] fields = {{1, 1}, {7, 9}, {6, 10}, {2, 4}, {3, 5}, {6, 10}};
        int[][] fields = {{1, 1}, {7, 9}, {6, 10}, {2, 4}, {3, 8}, {6, 10}};
        int n = 10; // 油量限制
        int maxProfit = maxProfitWithDP(fields, n);
        System.out.println("在给定油量 " + n + " 的情况下，最大收益为: " + maxProfit);
    }

    // 使用动态规划计算在给定油量下的最大收益
    public static int maxProfitWithDP(int[][] fields, int n) {
        int[] dp = new int[n + 1]; // dp[i] 表示在油量 i 下能够获得的最大收益

        for (int[] field : fields) {
            int cost = field[0]; // 获取当前地块的耗油量
            int profit = field[1]; // 获取当前地块的收益

            // 遍历所有可能的油量，更新最大收益
            for (int i = n; i >= cost; i--) {
                dp[i] = Math.max(dp[i], dp[i - cost] + profit);
            }
        }

        return dp[n]; // 返回在油量 n 下的最大收益
    }
    public static int maxProfitWithDP2(int[][] fields,int n){
        int[] dp = new int[n+1];
        for(int[] field:fields){
            int cost = field[0];//获取当前地块的耗油量
            int profit = field[1];//获取当前地块的收益
            //遍历所有可能的油量，更新最大收益
            for (int i = n; i >=cost ; i--) {
                dp[i] = Math.max(dp[i],dp[i-cost]+profit);
            }
        }
        return dp[n];
    }
}
